class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        if target <= 0:
            return res
        candidates.sort()
        self.dfs(res, [], candidates, 0, target)
        return res


    def dfs(self, res, temp, candidates, index, sum):
        if sum == 0:
            list = temp[:]#copy this array 
            res.append(list)
            return
        if sum < candidates[index]:
            return
        for i in range(index,len(candidates)):
            temp.append(candidates[i])
            self.dfs(res, temp, candidates, i, sum-candidates[i])
            temp.pop()
